"""
NC66 两个链表的第一个公共结点

https://www.nowcoder.com/practice/6ab1d9a29e88450685099d45c9e31e46?tpId=117&&tqId=37761&&companyId=239&rp=1&ru=/company/home/code/239&qru=/ta/job-code-high/question-ranking
"""


class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

#
#
# @param pHead1 ListNode类
# @param pHead2 ListNode类
# @return ListNode类
#


class Solution:

    def method1(self, pHead1, pHead2):
        """
        这个思路最简单，就是先遍历完一个链表，存起所有的节点（visited）
        再遍历另一个链接，找到第一个在visited中的节点，否则返回None

        时间复杂度：O(m+n)
        空间复杂度：O(m)
        """
        if not pHead1 or not pHead2:
            return

        visited1 = set()
        while pHead1:
            # 不能用pHead1.val，因为一个节点除了val还有next，必须都一样才行
            visited1.add(pHead1)
            pHead1 = pHead1.next

        while pHead2:
            if pHead2 in visited1:
                return pHead2

            pHead2 = pHead2.next

        return

    def method2(self, pHead1, pHead2):
        """
        双指针，可以看下走下面两个的情况
        [1, 2, 4, 5] + [3, 4,  5]
        [3, 4, 5] + [1, 2, 4, 5]
        只要比较对应位置上的节点是否相等即可。最后会返回[4, 5]

        时间复杂度：O(m+n)
        空间复杂度：O(1)
        """

        if not pHead1 or not pHead2:
            return

        # 不要直接在pHead1和pHead2上操作，因为要保留这两个节点
        # 在其中一个遍历完成后，切换到另一个链表上
        node1, node2 = pHead1, pHead2
        while node1 != node2:
            if node1:
                node1 = node1.next
            else:
                # 注意，这里切换到链表2了
                node1 = pHead2

            if node2:
                node2 = node2.next
            else:
                node2 = pHead1

        return node1

    def FindFirstCommonNode(self, pHead1, pHead2):
        # write code here
        return self.method2(pHead1, pHead2)
